package com.lw.leetcode.sort.c;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 778. 水位上升的泳池中游泳
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/25 20:42
 */
public class SwimInWater {

    public static void main(String[] args) {
        SwimInWater test = new SwimInWater();

        // 3
//        int[][] grid = {{0, 2}, {1, 3}};

        // 16
        int[][] grid = {{0, 1, 2, 3, 4}, {24, 23, 22, 21, 5}, {12, 13, 14, 15, 16}, {11, 17, 18, 19, 20}, {10, 9, 8, 7, 6}};

        int i = test.swimInWater(grid);
        System.out.println(i);
    }

    public int swimInWater(int[][] grid) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int length = grid.length;
        if (length == 1) {
            return 0;
        }
        int v = grid[0][0];
        queue.add(v << 16);
        grid[0][0] = -1;
        int[][] arr = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int count = 0;
        li:
        while (!queue.isEmpty()) {
            v = queue.poll();
            int val = v >> 16;
            if (val > count) {
                count = val;
            }
            int x = (v >> 8) & 0XFF;
            int y = v & 0XFF;
            for (int[] ints : arr) {
                int a = x + ints[0];
                int b = y + ints[1];
                if (a < 0 || b < 0 || a == length || b == length) {
                    continue;
                }
                int t = grid[a][b];
                grid[a][b] = -1;
                if (t == -1) {
                    continue;
                }
                if (a == length - 1 && b == length - 1) {
                    count = Math.max(count, t);
                    break li;
                }
                queue.add((t << 16) + (a << 8) + b);
            }
        }
        return count;
    }

}
